package LearnDataStructure.c_树结构.例题;

import LearnDataStructure.c_树结构.BSTNode;
import LearnDataStructure.c_树结构.有序树.二叉树.b_MyBinaryTreebyLinked;
/**
 * @version: 1.0
 * @Author: wuqiu
 * @date: 2023-07-13 13:01
 * @description: LeetcodeLearnAlgorithm -> LearnDataStructure.c_树结构.例题
 */
/*
求两个节点的最近公共祖先节点
规定1：如果两个节点是父子关系，那么父节点就是最近公共祖先节点
贵定2：如果两个节点是相同节点，那么它们互为最近公共祖先节点
 */
public class j_求LCA {
    public static void main(String[] args) {
        j_求LCA test = new j_求LCA();
        b_MyBinaryTreebyLinked<Integer,Integer> binaryTree = new b_MyBinaryTreebyLinked<Integer,Integer>();
        binaryTree.insert(6,6);
        binaryTree.insert(7, 7);
        binaryTree.insert(4,4);
        BSTNode<Integer, Integer> q = binaryTree.insert(5, 5);
        binaryTree.insert(8, 8);
        BSTNode<Integer, Integer> p = binaryTree.insert(2, 2);

        System.out.println(binaryTree);
        Integer result = test.useGetLCA(binaryTree.getRoot(), p, q);
        System.out.println(result);





        b_MyBinaryTreebyLinked<Integer,Integer> binaryTree2 = new b_MyBinaryTreebyLinked<>();

        binaryTree2.insert(6,6);
        BSTNode<Integer, Integer> node1 = binaryTree2.insert(7, 7);
        binaryTree2.insert(4,4);
        binaryTree2.insert(5,5);
        BSTNode<Integer, Integer> node = binaryTree2.insert(8, 8);
        binaryTree2.insert(2,2);

        System.out.println(binaryTree2);
        Integer lca = test.getLCA2(binaryTree2.getRoot(), node, node1);
        System.out.println(lca);
    }

    public Integer useGetLCA(BSTNode<Integer,Integer> root,BSTNode<Integer,Integer> key1, BSTNode<Integer,Integer> key2) {
        // BSTNode<Integer,Integer> result = getLCA(root, key1, key2);
        BSTNode<Integer,Integer> result = getLCAPlus(root, key1, key2);
        return result == null ? -1 : result.value;
    }

    /**
     * 递归；不使用额外数据结构
     * @param node
     * @param p
     * @param q
     * @return
     */
    private BSTNode<Integer, Integer> getLCA(BSTNode<Integer, Integer> node, BSTNode<Integer, Integer> p, BSTNode<Integer, Integer> q) {
        if (node == null) {
            return null;
        }
        if (p.equals(q)) {
            return p;
        }
        if (node.equals(p) || node.equals(q)) {
            return node;
        }
        boolean isPLeft = cover(node.left, p);//p是否在左
        boolean isQRight = cover(node.right, q);//q否在右

        if (isPLeft == isQRight) {
            /*
            p左q右，同true
            p右q左，同false
            反正在node两侧
            那么node一定是最近公共祖先！
            质疑前请画画图！
             */
            return node;
        } else if (isPLeft) {//p左q左
            return getLCA(node.left,p,q);
        } else {
            return getLCA(node.right,p,q);
        }
    }

    /**
     * 判断node为根节点的子树，是否含有target节点
     * @param node
     * @param target
     * @return
     */
    private boolean cover(BSTNode<Integer, Integer> node, BSTNode<Integer, Integer> target) {
        if (node == null) {
            return false;
        }
        if (node.equals(target)) {
            return true;
        }
        return cover(node.left, target) || cover(node.right, target);
    }

    /**
     * 相较于getLCA,性能上有一些优势
     * @param node
     * @param p
     * @param q
     * @return
     */
    private BSTNode<Integer, Integer> getLCAPlus(BSTNode<Integer, Integer> node, BSTNode<Integer, Integer> p, BSTNode<Integer, Integer> q) {
        if (node == null) {
            return null;
        }
        if (node.equals(p) && node.equals(q)) {//p == q的情况
            return node;
        }

        BSTNode<Integer, Integer> leftRes = getLCAPlus(node.left, p, q);
        /*
        leftRes的结果有四种
        是lca，
        是p（p在这一侧），
        是q（q在这一侧），
        是null（pq都不在这一侧）
         */
        if (leftRes != null && !leftRes.equals(p) && !leftRes.equals(q)) {//如果leftRes就是lca，进入判断
            return leftRes;
        }

        BSTNode<Integer, Integer> rightRes = getLCAPlus(node.right, p, q);
        if (rightRes != null && !rightRes.equals(p) && !rightRes.equals(q)) {
            return rightRes;
        }

        if (leftRes !=null && rightRes !=null) {//node两边各找到一个，一般情况
            return node;//那么node就必然是lca,因为是     向下向范围递减递归，     可以自己去画画图理解理解。
        } else if (node.equals(p) || node.equals(q)) {//因为先递归后判断，所以node节点与p,q的比较放到了这里
            return node;
        } else {
            return leftRes == null ? rightRes : leftRes;//左右子树递归结果有一个不为null，则返回“不是null”的结果；都为null，返回null
        }
    }

    /**
     * 递归，使用额外数据结构,不使用parent
     * @param node
     * @param p
     * @param q
     * @return
     */
    public Integer getLCA2(BSTNode<Integer,Integer> node, BSTNode<Integer,Integer> p, BSTNode<Integer,Integer> q) {
        getLCAthis(node, p);
        getLCAother(node,q);
        LinkedNodeTwoWay<Integer> headOfp = headP;
        LinkedNodeTwoWay<Integer> headOfq = headQ;
        int countp = 0;
        int countq = 0;
        while (headOfp != null) {
            countp++;
            headOfp = headOfp.next;
        }
        while (headOfq != null) {
            countq++;
            headOfq = headOfq.next;
        }
        int num = 0;
        if (countp > countq) {
            num = countp - countq;
            headOfp = headP;
            headOfq = headQ;
            for (int i = 0; i < num; i++) {
                headOfp = headOfp.next;
            }
        } else {
            num = countq - countp;
            headOfp = headP;
            headOfq = headQ;
            for (int i = 0; i < num; i++) {
                headOfq = headOfq.next;
            }
        }
        while (!headOfp.date.equals(headOfq.date) && headOfp != null && headOfq != null) {
            headOfp = headOfp.next;
            headOfq = headOfq.next;
        }
        return headOfp == null ? -1 : headOfp.date;
    }

    private LinkedNodeTwoWay<Integer> headP = null;
    private LinkedNodeTwoWay<Integer> tailP = null;
    private LinkedNodeTwoWay<Integer> headQ = null;
    private LinkedNodeTwoWay<Integer> tailQ = null;

    public LinkedNodeTwoWay<Integer> getLCAthis(BSTNode<Integer,Integer> node, BSTNode<Integer,Integer> target) {
        if (node == null) {
            return null;
        }

        if (node == target) {
            headP = new LinkedNodeTwoWay<Integer>(node.value);
            tailP = headP;
            return tailP;
        }

        LinkedNodeTwoWay<Integer> left = getLCAthis(node.left, target);
        LinkedNodeTwoWay<Integer> right = getLCAthis(node.right, target);

        if (left == null && right == null) {
            return null;
        }

        tailP.next = new LinkedNodeTwoWay<Integer>(node.value);
        tailP = tailP.next;
        return tailP;
    }

    public LinkedNodeTwoWay<Integer> getLCAother(BSTNode<Integer,Integer> node, BSTNode<Integer,Integer> target) {
        if (node == null) {
            return null;
        }

        if (node == target) {
            headQ = new LinkedNodeTwoWay<Integer>(node.value);
            tailQ = headQ;
            return tailQ;
        }

        LinkedNodeTwoWay<Integer> left = getLCAother(node.left, target);
        LinkedNodeTwoWay<Integer> right = getLCAother(node.right, target);

        if (left == null && right == null) {
            return null;
        }

        tailQ.next = new LinkedNodeTwoWay<Integer>(node.value);
        tailQ = tailQ.next;
        return tailQ;
    }
}
